package BFS解决拓扑排序;

import java.util.*;

public class test1 {
    /**建图很重要!!!!!!!在图的基础上做BFS
     * 有向无环图(DAG图)
     *      不仅仅只是看有没有边,还要看边指向的方向,是否是一个可以跟着方向走的无环
     *      入度: 某一顶点有多少条边指向他  出度: 某一顶点,有多少条边从该顶点出去
     *
     *
     * 顶点活动图(AOV网)  有向无环图的一种应用
     *      在有向无环图中,用顶点来表示不同活动,用边来表示活动的先后顺序-->流程图
     *
     *
     * 拓扑排序
     *      找到做事情的先后顺序  同时结果可能不是唯一的
     *      如何排序:
     *          先找入度为0的点,然后删除边(重复操作) 直到 没有点 或者 没有入度为0的点为止(有环)
     *
     * 实现排序:
     *      借助队列:来一次BFS
     *          1.初始化:将所有入度为0的点加入到队列中
     *          2.当队列不为空:
     *              (1)拿出队头元素,加入到最终结果中
     *              (2)删除与该元素相连的边
     *              (3)判断删完后与删除边相连的点入度是否变为0,为0加入到队列中,一直循环
     */

    public boolean canFinish(int n, int[][] p) {
        //如果给的是字符串,就要先映射为数字
        /**
         * 建图
         * 数据量稠密: 邻接表
         *      一条链表示链表头分别链接了后续的每一个节点
         *      List<List<Integer>> edges;
         *      Map<Integer,List<Integer>> edges; --> 用哈希表的形式 --> 万能,不需要数据提前映射
         * 如何找到入度? 用一个矩阵 int[] in = new int[n];
         */


        // 1.准备工作
        int[] in = new int[n];
        Map<Integer, List<Integer>> edges = new HashMap<>(); //邻接表存图

        // 2.建图
        for (int i = 0; i < p.length; i++) {
            int a = p[i][0],b=p[i][1]; // b->a
            if(!edges.containsKey(b))
                edges.put(b,new ArrayList<>());
            edges.get(b).add(a);
            in[a]++;
        }

        // 3.拓扑排序
        // 先把入度为0的加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if(in[i]==0) queue.add(i);
        }

        // bfs
        while (!queue.isEmpty()){
            int t = queue.poll();
            for (int x:edges.getOrDefault(t,new ArrayList<>())) {
                in[x]--; // 删除边
                if(in[x]==0) queue.add(x);
            }
        }

        // 判断是否有环
        for (int y:in) {
            if(y!=0) return false;
        }
        return true;
    }
}
